package com.example.backtrack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 78. 子集  和77. 组合是一摸一样的，只不过!!!不需要!!!目标数组大小的控制，所以每一轮循环都加入res即可
 * 给你一个整数数组 nums ，数组中的元素 !!!互不相同!!!（数组不重复，子集一定不会重复） 。返回该数组所有可能的子集（幂集）。
 * <p>
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * 示例 2：
 * <p>
 * 输入：nums = [0]
 * 输出：[[],[0]]
 */
public class SubSets {
    /**
     * 存放符合条件结果的集合
     */
    List<List<Integer>> result = new ArrayList<>();
    /**
     * 用来存放符合条件结果
     */
    LinkedList<Integer> path = new LinkedList<>();
    int[] nums;

    public static void main(String[] args) {
        SubSets subSets = new SubSets();
        int[] nums = {1, 2};
        System.out.println(subSets.subsets(nums));
    }

    public List<List<Integer>> subsets(int[] nums) {
        if (nums.length == 0) {
            //result.add(new ArrayList<>());
            return result;
        }
        this.nums = nums;
        subsetsHelper(0);
        return result;
    }

    private void subsetsHelper(int startIndex) {
        //「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
        result.add(new ArrayList<>(path));
        //终止条件可不加
        //这里限制当result加入最全的nums时，这个循环的判断条件会终止，即startindex==length开始回溯过程
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            /**注意 这里是i+1！！！！！ 因为i代表着最新值，而start在循环中一直不变*/
            subsetsHelper(i + 1);
            path.removeLast();
        }
    }
}
